The next generation communication system has developed into a packet service communication system. The packet service communication system, a system (e.g., one or more base stations) for transmitting burst packet data to multiple mobile stations, has been designed to be suitable for high-capacity data transmission. The next generation communication system considers using, as channel codes, not only the turbo codes but also the Low Density Parity Check (LDPC) codes, which are known to have good performance gain for high-speed data transmission and can increase reliability of data transmission by effectively correcting errors caused by the noises generated in a transmission channel. The next generation communication system, considering using the LDPC codes, includes an Institute of Electrical and Electronics Engineers (IEEE) 802.16e communication system and an IEEE 802.11n communication system.
With reference to FIG. 1, a description will now be made of a structure of a signal transmission apparatus in a general communication system using LDPC codes.
FIG. 1 illustrates a structure of a signal transmission apparatus (e.g., a base station) in a general communication system using LDPC codes.
Referring to FIG. 1, the signal transmission apparatus includes an encoder 111, a modulator 113, and a transmitter 115. The information data (or information vector, s) that the signal transmission apparatus intends to transmit, is delivered to the encoder 111. The encoder 111 encodes the information vector s with a predetermined encoding scheme to generate a codeword vector c, or LDPC codeword, and outputs the codeword vector c to the modulator 113. The encoding scheme is herein an LDPC encoding scheme. The modulator 113 modulates the codeword vector c with a predetermined modulation scheme to generate a modulation vector m, and outputs the modulation vector m to the transmitter 115. The transmitter 115 performs transmission signal processing on the modulation vector m output from the modulator 113, and transmits the resulting signal to a signal reception apparatus via an antenna ANT.
Next, with reference to FIG. 2, a description will be made of a structure of a signal reception apparatus in a general communication system using LDPC codes.
FIG. 2 illustrates a structure of a signal reception apparatus (e.g., a mobile station) in a general communication system using LDPC codes.
Referring to FIG. 2, the signal reception apparatus includes a receiver 211, a demodulator 213, and a decoder 215. The signal transmitted by the signal transmission apparatus is received at the signal reception apparatus via an antenna ANT, and the received signal is delivered to the receiver 211. The receiver 211 performs reception signal processing on the received signal to generate a received vector r, and outputs the received vector r to the demodulator 213. The demodulator 213 demodulates the received vector r output from the receiver 211 with a demodulation scheme corresponding to the modulation scheme used in the modulator 113 of the signal transmission apparatus, and outputs the resulting demodulation vector x to the decoder 215. The decoder 215 decodes the demodulation vector x output from the demodulator 213 with a decoding scheme corresponding to the encoding scheme used in the encoder 111 of the signal transmission apparatus, and outputs the decoded signal as the finally restored information vector ŝ. Herein, an iterative decoding algorithm based on a sum-product algorithm or a min-sum algorithm is popularly used for the decoding scheme, or LDPC decoding scheme, and a detailed description of the sum-product algorithm and the min-sum algorithm will be given below.
The LDPC code is a code defined by a parity check matrix in which major elements have a value of ‘0’ and minor elements except for the elements having a value of ‘0’ have a non-zero value, for example, a value of ‘1’. The LDPC code can be expressed with a bipartite graph, and the bipartite graph is a graph expressed with variable nodes, check nodes, and edges connecting the variable nodes to the check nodes.
The LDPC code can be decoded using the sum-product algorithm-based iterative decoding algorithm in the bipartite graph. The sum-product algorithm is a kind of a message passing algorithm, and the ‘message passing algorithm’ refers to an algorithm for exchanging messages over edges in the bipartite graph, and calculating and updating output messages from the messages being input to the variable nodes or check nodes. Therefore, a decoder for decoding the LDPC code, it uses the message passing algorithm-based iterative decoding algorithm, has lower complexity and can be easily realized with a parallel-processing decoder, compared with the decoder for the turbo code.
Next, with reference to FIG. 3, a description will be made of a message passing operation in an arbitrary check node of a decoder using a general LDPC decoding scheme (hereinafter referred to as an ‘LDPC decoder’).
FIG. 3 illustrates a message passing operation in an arbitrary check node of a general LDPC decoder.
In FIG. 3, there are included a check node m 300 and multiple variable nodes 310, 320, 330 and 340 connected to the check node m 300. Further, Tn′,m indicates a message passed (or transferred) from the variable node n′ 310 to the check node m 300, and En,m indicates a message passed from the check node m 300 to the variable node n 330. Herein, a set of all variable nodes connected to the check node m 300 is defined as N(m), and a set given by excluding the variable node n 330 from N(m) is defined as N(m)\n. In this case, a message update rule based on the sum-product algorithm can be expressed as Equation 1:
                                          Sign            ⁡                          (                              E                                  n                  ,                  m                                            )                                =                                    ∏                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ⁢                                      \                    ⁢                    n                                                                        ⁢                          Sign              ⁡                              (                                  T                                                            n                      ′                                        ,                    m                                                  )                                                    ⁢                                  ⁢                                                        E                              n                ,                m                                                          =                      Φ            [                                          ∑                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              Φ                ⁡                                  (                                                                                T                                                                        n                          ′                                                ,                        m                                                                                                  )                                                      ]                                              [                  Eqn          .                                          ⁢          1                ]            
In Equation 1, Sign(En,m) denotes a sign of a message En,m, |En,m| denotes an magnitude of a message En,m, and a function Φ(x) can be expressed as Equation 2:
                              Φ          ⁡                      (            x            )                          =                  -                      log            ⁡                          [                              tanh                ⁡                                  (                                      x                    2                                    )                                            ]                                                          [                  Eqn          .                                          ⁢          2                ]            
A message update rule based on the min-sum algorithm can be expressed as Equation 3:
                                          Sign            ⁡                          (                              E                                  n                  ,                  m                                            )                                =                                    ∏                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ⁢                                      \                    ⁢                    n                                                                        ⁢                          Sign              ⁡                              (                                  T                                                            n                      ′                                        ,                    m                                                  )                                                    ⁢                                  ⁢                                                        E                              n                ,                m                                                          =                                                    min                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                              {                                                                        T                                                                  n                        ′                                            ,                      m                                                                                        }                                      =                                                        T                                                      n                    0                                    ,                  m                                                                                                      [                  Eqn          .                                          ⁢          3                ]            
In Equation 3, n0 can be rewritten as Equation 4:
                              n          0                ⁢                              Arg            ⁢            min                                              n              ′                        ∈                                          N                ⁡                                  (                  m                  )                                            ⁢                              \                ⁢                n                                                    ⁢                  {                                                T                                                n                  ′                                ,                m                                                          }                                    [                  Eqn          .                                          ⁢          4                ]            
Although an input/output message of each node is used without an absolute sign of Equation 1, Equation 3 or Equation 4, a magnitude of the message can be expressed.
Next, with reference to FIG. 4, a description will be made of an input/output message passing operation in an arbitrary check node of an LDPC code generated in a general LDPC decoder.
FIG. 4 illustrates an internal structure of a general LDPC decoder.
Referring to FIG. 4, a description will be made of an input/output message passing operation for a check node. A check node operator of the LDPC decoder includes a first memory 400, a check node processor 410, and a second memory 420. The first memory 400 stores the messages to be input to the check node processor 410. The second memory 420 stores the messages output from the check node processor 410. Further, the first memory 400 includes a plurality of, for example, dc sub-memories, i.e., a sub-memory #1 Tn1,m (400-1) to a sub-memory
  #  ⁢      d    c    ⁢          ⁢      T                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              400        ⁢                  -                ⁢                  d          c                    )        .  The second memory 420 includes a plurality of, for example, dc sub-memories, i.e., a sub-memory #1 En1,m (420-1) to a sub-memory
  #  ⁢      d    c    ⁢          ⁢      E                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              420        ⁢                  -                ⁢                  d          c                    )        .  
If an input degree of the check node processor 410 is assumed to be dc, the dc input messages are stored in the sub-memory #1 Tn1,m (400-1) to the sub-memory
      #    ⁢          d      c        ⁢                  ⁢          T                                    n                          d              c                                ,          m                ⁢                                        ⁢                  ⁢          (              400        ⁢                  -                ⁢                  d          c                    )        ,and output messages associated with the dc input messages are stored in the sub-memory #1 En1,m (420-1) to the sub-memory
  #  ⁢      d    c    ⁢          ⁢      E                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              420        ⁢                  -                ⁢                  d          c                    )        .  
As described above, the check node processor 410 performs the message passing operation based on the min-sum algorithm using Equation (3). That is, the check node's output messages En1,m (420-1), En2,m (420-2), En3,m (420-3) and
      E                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢      (          420      ⁢              -            ⁢              d        c              )  are calculated using Equation (3). The output message En1,m (420-1) is calculated using the remaining dc−1 messages except for the input message Tn1,m (400-1) among the dc input messages Tn1,m (400-1), Tn2,m (400-2), Tn3,m (400-3) and
      T                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              400        ⁢                  -                ⁢                  d          c                    )        .  The output message En2,m (420-2) is calculated using the remaining dc−1 messages except for the input message Tn2,m (400-2) among the dc input messages Tn1,m (400-1), Tn2,m (400-2), Tn3,m (400-3) and
      T                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              400        ⁢                  -                ⁢                  d          c                    )        .  The output message En3,m (420-3) is calculated using the remaining dc−1 messages except for the input message Tn3,m (400-3) among the dc input messages Tn1,m (400-1), Tn2,m (400-2), Tn3,m (400-3) and
      T                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢            (              400        ⁢                  -                ⁢                  d          c                    )        .  
The output messages En1,m (420-1), En2,m (420-2), En3,m (402-3) and
      E                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢      (          420      ⁢              -            ⁢              d        c              )  calculated by Equation (3) in this manner are input to dc variable nodes n1, n2, n3, . . . , ndc, respectively.
Table 1 shows input/output values of the messages, obtained when an operation of a dc=9 check node is performed using the min-sum algorithm.
TABLE 1iTn1,mTn2,mTn3,mTn4,mTn5,mTn6,mTn7,mTn8,mTn9,mEn1,m137291536412372915364133729153641437291536415372915364263729153641737291536418372915364193729153641
In Table 1, values of the dc=9 messages being input to the check node m are Tn1,m=3, Tn2,m=7, Tn3,m=2, Tn4,m=9, Tn6,m=1, Tn6,m=5, Tn7,m=3, Tn8,m=6, and Tn9,m=4, respectively. The message En1,m output from the check node processor 410 can be calculated using the remaining 8 messages except for the input message Tn1,m among the 9 input messages. If the min-sum algorithm is used, because the minimum value among the values of the remaining 8 messages is Tn5,m=1, En1,m is 1 (En1,m=1). In this manner, values of the output messages En1,m (420-1) to
      E                            n                      d            c                          ,        m            ⁢                            ⁢          ⁢      (          420      ⁢              -            ⁢              d        c              )  can be calculated.
As described above, when the check node processor performs the operation using the min-sum algorithm, it needs many operations to calculate the output messages, considerably increasing the complexity. Therefore, there is a need for a check node processor for reducing the complexity when performing the operation of the check node using the min-sum algorithm.